package 我的Java学习_算法基础.day_03;

public class _053_排序数组中找和的因子 {
    public static void main(String[] args) {
        int[] arr= {-8,-4,-3,0,2,4,5,8,9,10};
        String s = findTowPointer(arr,0,arr.length-1,10);
        System.out.println(s);
        s = findBinarySearch(arr,0,arr.length-1,10);
        System.out.println(s);
    }


    /**
     * 给定已经排序数组arr和k，不重复打印arr中所有相加和为k的不降序二元数组
     *
     * 如输入arr= {-8,-4,-3,0,2,4,5,8,9,10}，k=10
     *
     * 输出（0，10），（2，8）
     * @param array 待查询数组
     * @param begin 开始元素下标
     * @param end   结束元素下标
     * @param k     两数和
     * @return      全部满足条件二元组
     */
    private static String findTowPointer(int[] array, int begin, int end, int k){
        int left = begin,right = end;
        String find = new String();
        StringBuilder s = new StringBuilder("(");
        while(left<right){
            int leftNumber = array[left],rightNumber = array[right];
            if(leftNumber+rightNumber==k){
                s.append(leftNumber+","+rightNumber+")");
                find=find+s.toString();
                s=new StringBuilder("(");
                right--;
            }else if(leftNumber+rightNumber<k){
                left++;
            }else{
                right--;
            }
        }
        return find;
    }
    private static String findBinarySearch(int[] array,int begin,int end,int key){
        String find = new String();
        int midIndex = begin+((end-begin)>>1);
        int mid = array[midIndex];
        for(int i = 0;i<array.length-1;i++){
            int brother = key - array[i];
            int flag=binarySearch(array,i+1,array.length-1,brother);
            if(flag!=-1){
                StringBuilder s = new StringBuilder("(");
                s.append(array[i]+","+brother+")");
                find=find+s.toString();
            }
        }
        return find;
    }
    private static int binarySearch(int[] array,int begin,int end, int key){
        if(begin>end){
            return -1;
        }
        int mid = begin+((end-begin)>>1);
        int midVal = array[mid];
        if(key==midVal){
            return key;
        }else if(key>midVal){
            return binarySearch(array,mid+1,end,key);
        }else{
            return binarySearch(array,begin,mid-1,key);
        }
    }
}
